package basic.sort.violence;

/**
 * @author distantstar
 * @version 1.0
 * @date 2021
 * @description basic.sort.violence
 * @since JDK1.8
 * 
 * 给定一个整型数组arr，代表数值不同的纸牌排成一条线，
 * 玩家A和玩家B依次拿走每张纸牌，
 * 规定玩家A先拿，玩家B后拿，
 * 但是每个玩家每次只能拿走最左或最右的纸牌，
 * 玩家A和玩家B都绝顶聪明。请返回最后获胜者的分数。
 */
public class CardLine {

    /**
     * 先手可以获得的最大分数
     * @param arr 分数数组
     * @param l 有效左范围
     * @param r 有效右范围
     * @return 返回范围内可获得的最大分数
     */
    private static int firstHand(int[] arr, int l, int r) {
        // 当只剩一张牌时，先手直接获取该牌分数
        if (l == r) {
            return arr[l];
        }

        // 获取此时先手获得的分数和后手获得的分数最大值
        return Math.max(arr[l] + backHand(arr, l + 1, r), arr[r] + backHand(arr, l, r - 1));
    }

    /**
     * 后手可以获得的最大分数
     * @param arr 分数数组
     * @param l 有效左范围
     * @param r 有效右范围
     * @return 返回范围内可获得的最小分数
     */
    private static int backHand(int[] arr, int l, int r) {
        // 当只剩一张牌时，后手无法获得任何分数
        if (l == r) {
            return 0;
        }

        // 当是后手时，对面一定会在让你下一次先手获得的分数最小
        return Math.min(firstHand(arr, l + 1, r), firstHand(arr, l, r - 1));
    }

    private static int win1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        // 获取决定第一步是先手还是后手的最大分数
        return Math.max(firstHand(arr, 0, arr.length - 1),
                backHand(arr, 0, arr.length - 1));
    }

    /**
     * 动态规划解
     * 定义两个结构化二维数组，f[][], b[][]
     *
     * @param arr 源数组
     * @return 返回先后手最大值
     */
    private static int winDp(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }

        // 数组长度
        int n = arr.length;
        // 定义两个结构化数组
        int[][] f = new int[n][n];
        int[][] s = new int[n][n];

        // l == r赋值
        for (int i = 0; i < n; i++) {
            f[i][i] = arr[i];
        }

        // 循环一步一步填充各个位置上可获得的分数
        for (int col = 1; col < n; col++) {
            int l = 0;
            int r = col;
            while (r < n) {
                // 参照尝试过程
                f[l][r] = Math.max(arr[l] + s[l + 1][r], arr[r] + s[l][r - 1]);
                s[l][r] = Math.min(f[l + 1][r], f[l][r - 1]);
                l++;
                r++;
            }
        }

        return Math.max(f[0][n - 1], s[0][n - 1]);
    }

    public static int[] generateRandomArray(int maxSize, int maxValue) {
        int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) ((maxValue + 1) * Math.random());
        }
        return arr;
    }

    public static void main(String[] args) {
        int maxSize = 40;
        int maxValue = 100;
        int[] arr = generateRandomArray(maxSize, maxValue);

//        int[] arr = { 5, 7, 4, 5, 8, 1, 6, 0, 3, 4, 6, 1, 7 };
        long start = System.currentTimeMillis();
        System.out.println(winDp(arr));
        long end = System.currentTimeMillis();
        System.out.println("dp cost time: " + (end - start) + "ms");
        start = System.currentTimeMillis();
        System.out.println(win1(arr));
        end = System.currentTimeMillis();
        System.out.println("violence cost time: " + (end - start) + "ms");
    }
}
